package leetcode_21_40;

import utils.ListNode;

import java.util.Comparator;
import java.util.PriorityQueue;

public class mergeKLists_23 {
    /**
     * 将所有链表合并到一个升序链表中，返回合并后的链表
     * 按顺序两两合并链表
     * 太慢了，98ms
     * @param lists
     * @return
     */
    public static ListNode mergeKLists(ListNode[] lists) {
        ListNode l=null;
        for(int i=0;i<lists.length;i++){
            if(lists[i]==null)
                continue;
            l=mergeTwoLists(l,lists[i]);
        }
        return l.next;
    }

    /**
     * 分治合并
     * 每轮两两配对合并，使数量减半
     * 直到最后剩余一个
     * 维护两个指针同时进位，速度显然更快
     * @param lists
     * @return
     */
    public static ListNode mergeKLists2(ListNode[] lists) {
        ListNode result=merging(lists,0,lists.length-1);
        return result;
    }
    /**
     * 递归合并
     * 每一层递归，l-mid  和  mid-r  两个区间同时进行
     * @return
     */
    public static ListNode merging(ListNode[] lists,int l,int r){
        if(l==r)                      //当l==r 时，就是最后一层递归，自己不需要和自己合并，直接返回一个
            return lists[l];
        int mid= ( l + r ) / 2 ;
        return mergeTwoLists(merging(lists,l,mid),merging(lists,mid+1,r));
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode result=new ListNode();
        ListNode root=result;
        while (list1 != null || list2 != null){
            if(list1 == null ){
                root.next=list2;
                break;
            } else if (list2 == null) {
                root.next=list1;
                break;
            } else if( list1.val < list2.val || list2 == null) { //如果链表1此时节点小于链表2此时节点,或者链表2已经遍历完
                root.next =  list1 ;                           //添加链表1此时节点，并且链表1向后遍历
                list1 = list1.next;
            }else{
                root.next =  list2;
                list2 = list2.next;
            }
            root=root.next;
        }
        return result.next;
    }


    /**
     * 使用PriorityQueue优先队列解法
     *
     * 容量为K的最小堆优先队列，把链表的头结点都放进去
     * 然后出队当前优先队列中最小的，挂上链表，
     * 然后让出队的那个节点的下一个入队
     * 再出队当前优先队列中最小的，直到优先队列为空。
     *
     * 方法不是特别快，但简洁易懂
     * @param lists
     * @return
     */
    public ListNode mergeKLists3(ListNode[] lists) {

        if (lists.length == 0) {
            return null;
        }

        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) { //队列内部按照var值排序
                return o1.val - o2.val;
            }
        });

        for (ListNode list : lists) {
            if (list == null) {
                continue;
            }
            pq.add(list);                                         //链表的头结点都放进去
        }

        while (!pq.isEmpty()) {
            ListNode nextNode = pq.poll();      //出队当前优先队列中最小的，挂上链表，
            curr.next = nextNode;
            curr = curr.next;
            if (nextNode.next != null) {
                pq.add(nextNode.next);              //让出队的那个节点的下一个入队，进行循环判断
            }
        }
        return dummyHead.next;
    }
}
